package com.dmzc.binarysearch;

//掌握二分查找的各种变体
public class BinarySearch {
    public static void main(String args[]) {
        //binarySearch1測試
        int[] arr = {1, 2, 4, 7, 8, 11, 21, 45, 78};
        int[] arr1 = {1, 2, 2, 3, 4, 6, 7, 8, 9, 9};
        System.out.println(binarySearch1(arr, 798));
        System.out.println(binarySearch2(arr, 0, arr.length - 1, 8));
        System.out.println(binarySearch3(arr1, 2));
        System.out.println(binarySearch3(arr1, 9));
        System.out.println(binarySearch4(arr1, 2));
        System.out.println(binarySearch4(arr1, 9));
    }

    //1.元素不重複
    public static int binarySearch1(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        //優化點，left+right可能會溢出,移位更加快速
        //while一定要考慮多通道的退出條件
//        int temp = (left + right) / 2;
        int temp = (left + (right - left) >> 1);
        int index = 0;
        //也可以比較left和right的值
        while (true)
            if (arr[temp] > num) {
                if (right == temp)
                    break;
                right = temp;
                temp = (left + (right - left) >> 1);
            } else if (arr[temp] < num) {
                if (left == temp)
                    break;
                left = temp;
                temp = (left + (right - left) >> 1);
            } else {
                index = temp;
                break;
            }
        return index;
    }

    //2.元素不重讀，遞歸解法
    public static int binarySearch2(int[] arr, int left, int right, int num) {
        if (left >= right)
            return 0;
        int temp = left + (right - left) >> 1;
        int index = 0;
        if (arr[temp] < num) {
            index = binarySearch2(arr, temp, right, num);
        } else if (arr[temp] > num) {
            index = binarySearch2(arr, left, temp, num);
        } else {
            return temp;
        }
        return index;
    }

    //3.对于存在重复元素，寻找第一个
    public static int binarySearch3(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        int temp = (left + (right - left) >> 1);
        int index = 0;
        while (true)
            if (arr[temp] > num) {
                if (right == temp)
                    break;
                right = temp;
                //不清楚优先级时一定要加上括号
                temp = (left + (right - left) >> 1);
            } else if (arr[temp] < num) {
                if (left == temp)
                    break;
                left = temp;
                temp = (left + ((right - left) >> 1));
            } else {
                //找到元素时，需要判断其前方是否还有相同的元素
                if (temp > 0 && arr[temp - 1] == num) {
                    right = temp - 1;
                    index = temp - 1;
                    temp = left + ((right - left) >> 1);
                } else {
                    index = temp;
                    break;
                }

            }
        return index;
    }

    //4.对于存在重复元素，寻找最后一个
    public static int binarySearch4(int[] arr, int num) {
        int left = 0;
        int right = arr.length - 1;
        int temp = (left + (right - left) >> 1);
        int index = 0;
        while (true)
            if (arr[temp] > num) {
                if (right == temp)
                    break;
                right = temp;
                temp = left + ((right - left) >> 1);
            } else if (arr[temp] < num) {
                if (left == temp)
                    break;
                left = temp;
                temp = left + ((right - left) >> 1);
            } else {
                //找到元素时，需要判断其前方是否还有相同的元素
                if (temp < arr.length - 1 && arr[temp + 1] == num) {
                    left = temp + 1;
                    index = temp + 1;
                    temp = left + ((right - left) >> 1);

                } else {
                    index = temp;
                    break;
                }

            }
        return index;
    }

    //5.寻找大于或等于某一个元素的第一个元素
    public static int binarySearch5(int arr, int num) {
        return 0;
    }

    //6.寻找小于或等于某一个元素的最后一个元素
    public static int binarySearch6(int arr, int num) {
        return 0;
    }
}
